#include <functional>
#include <algorithm>
#include "exacto.h"

CliqueMaximaFronteraExacto::CliqueMaximaFronteraExacto(const Grafo& g) : grafo(g) { }

set<uint> CliqueMaximaFronteraExacto::resolver(uint& frontera) {
	set<uint> cliques;
	set<uint> solucion;
	uint cantRes = 0;
	uint gradosR = 0;
	
	backtracking(cliques, gradosR, grafo.conjuntoNodos(), solucion, cantRes);
	frontera = cantRes;
	
	return solucion;
}

void CliqueMaximaFronteraExacto::backtracking(set<uint> &R, uint &gradosActuales, set<uint> P, set<uint> &res, uint &cantRes) {
	if(P.empty())
		return;

	set<uint> interseccion;
	int fronteraNueva;
	uint cantAristas = grafo.cantidadAristas();
	
	for(set<uint>::iterator it = P.begin(); it != P.end(); it++) {
		R.insert(*it);		
		gradosActuales += grafo.miGrado(*it);
		fronteraNueva = gradosActuales - R.size() * (R.size()-1);
		
		if(cantRes < fronteraNueva) {
			cantRes = fronteraNueva;
			res = R;		
		}
		
		if(cantRes == cantAristas - R.size()) {
			return;
		}
		
		interseccion = grafo.adyacentes(*it, P);
		backtracking(R, gradosActuales, interseccion, res, cantRes);

		R.erase(*it);
		gradosActuales -= grafo.miGrado(*it);
	}
}
